1. Field of the Invention
The invention generally relates to the field of error correction codes for communication systems, and in particular, the present invention relates to implementations of turbo decoding methods and systems.
2. Background of the Invention
In digital communication systems, information (such as data or voice) are transmitted through a channel which is often noisy. The noisy channel introduces errors in the information being transmitted such that the information received at the receiver is different from the information transmitted. To reduce the probability that noise in the channel could corrupt the transmitted information, communication systems typically employ some sort of error correction scheme. For instance, wireless data communication systems, operated in a low signal to noise ratio (SNR) environment, typically employ forward error correction (FEC) schemes. When FEC coding is used, the transmitted message is encoded with sufficient redundancies to enable the receiver to correct some of the errors introduced in the received message by noise in the communication channel.
Various FEC coding schemes are known in the art. In particular, turbo codes are a type of FEC codes that are capable of achieving better error performance than the conventional FEC codes. In fact, it has been reported that turbo codes could come within 0.7 dB of the theoretical Shannon limit for a bit error rate (BER) of 10−5. Because turbo codes can achieve exceptionally low error rates in a low signal-to-noise ratio environment, turbo codes are particularly desirable for use in wireless communications where the communication channels are especially noisy as compared to wired communications. In fact, the recent CDMA wireless communications standard includes turbo codes as one of the possible encoding scheme. For a detailed description of turbo coding and decoding schemes, see “Near Shannon limit error-correcting coding and decoding: Turbo-codes (1),” Berrou et al., Proc., IEEE Int'l Conf. on Communications, Geneva, Switzerland, pp. 1064-1070, 1993, and “Iterative decoding of binary block and convolutional codes,” Hagenauer et al., IEEE Trans. Inform. Theory, pp. 429-445, March 1996, which are incorporated herein by reference in their entireties. In brief, turbo codes are the parallel concatenation of two or more recursive systematic convolutional codes, separated by pseudorandom interleavers. Decoding of turbo codes involves an iterative decoding algorithm.
While turbo codes have the advantage of providing high coding gains, decoding of turbo codes is often complex and involves a large amount of complex computations. Turbo decoding is typically based on the maximum a posteriori (MAP) algorithm which operates by calculating the maximum a posteriori probabilities for the encoded data. While it has been recognized that the MAP algorithm is the optimal decoding algorithm for turbo codes, it is also recognized that implementation of the MAP decoding algorithm is very difficult in practice because of its computational complexities. To ease the computational burden of the MAP algorithm, approximations and modifications to the MAP algorithm have been developed. These include the Max-Log-MAP algorithm and the Log-MAP algorithm. The MAP, Max-Log-MAP and Log-MAP algorithms are described in detail in “A Comparison of Optimal and Sub-Optimal MAP Decoding Algorithms Operating in the Log Domain,” Robertson et al., IEEE Int'l Conf. on Communications (Seattle, Wash.), June, 1995, which is incorporated herein by reference in its entirety.
The MAP algorithm provides the logarithm of the ratio of the a posteriori probability (APP) of each information bit being “1” to the APP of the data bit being “0.” The probability value is given by equation (1) of Robertson et al. The computation of the APP requires computing the forward recursion (αk(·)), the backward recursion (βk(·)), and the branch transition probabilities (denoted γi(·) in Roberston et al.). To reduce the computational complexity of the MAP algorithm, the Max-Log-MAP and Log-MAP algorithms perform the entire decoding operation in the logarithmic domain. In the log domain, multiplication operations become addition operations, thus simplifying numeric computations involving multiplication. However, the addition operations in the non-log domain become more complex in the log domain. For example, the summation of two metric ex1 and ex2 is straight forward in the non-log domain and is accomplished by adding the two metric ex1+ex2. But in the log-map algorithm, the metric that is being calculated is x1 and x2. In order to add the two metric in the non-log domain, the metric x1 and x2 must first be converted to the non-log domain by taking the exponential, then adding the exponentiated metric, and finally taking the logarithm to revert back to the log domain. Thus, the sum of metric x1 and x2 is computed as: log(ex1+ex2). Equivalently, the computation can be rewritten as:log(ex1+ex2)=max(x1,x2)+log(1+e−|x1+x2|),  (i)which can be simplified by approximating the function log(1+e−|x1+x2|) by a look up table. Thus the approximation for the sum of the two metric is:log(ex1+ex2)≈max(x1,x2)+logtable(|x1−x2|),  (ii)where logtable(|x1−x2|) is an N-entry look up table. It has been shown that as few as 8 entries is sufficient to achieve negligible bit error or frame error degradation. The look-up table, logtable(|x1−x2|), is one-dimensional because the correction values only depend on the argument |x1−x2|. FIG. 1 illustrates an exemplary N-entry look-up table used in the computation of equation (ii) above in the Log-MAP decoding algorithm. In FIG. 1, look-up table 100 includes two data fields. Data field 102 includes N entries of the table indexes z, denoted as z0, z1, . . . , and ZN−1, where z is defined as |x1−x2|. Data field 104 includes the corresponding N entries of the computed table values of logtable(z), denoted as a0, a1, . . . , and aN−1, which are the computed values of the equation log(1+e−z). To address look-up table 100 for a given value of z, the value z is compared to the defined ranges of the table indexes z0, z1, . . . , and zN−1 to determine in which threshold range z belongs. The defined ranges of table thresholds are as follows:                              z          <                      z            1                          ,                                                                log              table                        ⁡                          (              z              )                                =                      a            0                          ,                                                      z            1                    ≤          z          <                      z            2                          ,                                                                log              table                        ⁡                          (              z              )                                =                      a            1                          ,                                                      z            2                    ≤          z          <                      z            3                          ,                                                                log              table                        ⁡                          (              z              )                                =                      a            2                          ,                        ⋮              ⋮                                                z                          N              -              1                                ≤          z                ,                                                  log            table                    ⁡                      (            z            )                          =                              a                          N              -              1                                .                    When the correct table threshold range is identified, for example, when z is within the range of z1 and z2 (data cell 103), the value a1 (data cell 105) will be returned by look-up table 100.
However, improvements to turbo decoding using the Log-MAP logarithms are desired to further reduce the complexity of the turbo decoder and to reduce the decoder processing time.